【二叉树打卡1】二叉搜索树的后序遍历序列

【题目】

输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。

【难度】

中

解答

一般对于二叉树的题目大多数都可以使用递归来做的，这道题也是用递归来多，思路如下：

二叉搜索树的后序序列有个这样的特点：序列的最后一个值为二叉树的根 root ；二叉搜索树左子树值都比 root 小，右子树值都比 root 大。

所以我们可以这样：

1、确定找出 root；

2、遍历序列（除去root结点），找到第一个大于root的位置，则该位置左边为左子树，右边为右子树；

3、遍历右子树，若发现有小于root的值，则是不符合二叉树搜索树的规则的，则直接返回false；

4、分别判断左子树和右子树是否仍是二叉搜索树（即递归步骤1、2、3）。

代码如下：

    public static boolean VerifySquenceOfBST(int [] sequence) {
        if(sequence == null || sequence.length < 1)
            return false;
        return judge(sequence, 0, sequence.length - 1);
    }

    private static boolean judge(int[] sequence, int left, int right) {
        // 只有一个节点，递归结束
        if(left >= right)
            return true;
        // 最右边的节点相当于根节点
        int t = sequence[right]; 
        // 用来记录序列中第一个比根节点大节点的下标
        int index = right;
        for (int i = left; i <= right - 1; i++) {
            // 找到根节点的右孩子
            if (sequence[i] > t) {
                index = i;
                i++;
                // 如果右子树中有比根节点还小的树的话，显然是不成立的。
                while (i <= right - 1) {
                    if(sequence[i] < t)
                        return false;
                    i++;
                }
            }
        }
        // 递归检查左右子树
        return judge(sequence, left, index - 1) && judge(sequence,index, right - 1);
    }

往期